package com.lw.leetcode.greedy.b;

/**
 * Created with IntelliJ IDEA.
 * 1888. 使二进制字符串字符交替的最少反转次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/15 13:16
 */
public class MinFlips {

    public static void main(String[] args) {
        MinFlips test = new MinFlips();

        // 2
//        String str = "01001001101";

        // 0
        String str = "010";

        int i = test.minFlips(str);
        System.out.println(i);
    }

    public int minFlips(String s) {
        int length = s.length();
        char[] chars = s.toCharArray();
        if ((length & 1) == 1) {
            return find(chars);
        }
        int count = 0;
        char c = '0';
        for (int i = 0; i < length; i++) {
            if (chars[i] != c) {
                count++;
            }
            c = (char) (97 - c);
        }
        return Math.min(count, length - count);
    }

    private int find (char[] chars) {
        int length = chars.length;
        int[] as = new int[length];
        int[] bs = new int[length];
        char a = '0';
        char b = '1';
        as[length - 1] = chars[length - 1] == a ? 0 : 1;
        bs[length - 1] = chars[length - 1] == b ? 0 : 1;
        a = (char) (97 - a);
        b = (char) (97 - b);
        for (int i = length - 2; i >= 0; i--) {
            if (chars[i] != a) {
                as[i] = as[i + 1] + 1;
            } else {
                as[i] = as[i + 1];
            }
            a = (char) (97 - a);
            if (chars[i] != b) {
                bs[i] = bs[i + 1] + 1;
            } else {
                bs[i] = bs[i + 1];
            }
            b = (char) (97 - b);
        }
        int sa = 0;
        int sb = 0;
        int max = Integer.MAX_VALUE;
         a = '0';
         b = '1';
        for (int i = 0; i < length - 1; i++) {
            if (chars[i] != a) {
                sa++;
            }
            if (chars[i] != b) {
                sb++;
            }
            boolean f = ((length - 1 - i) & 1) == 1;
            if (f) {
                if (a == '0') {
                    max = Math.min(max, Math.min(sa + as[i + 1], sb + bs[i + 1]));
                } else {
                    max = Math.min(max, Math.min(sa + bs[i + 1], sb + as[i + 1]));
                }
            } else {
                if (a == '1') {
                    max = Math.min(max, Math.min(sa + as[i + 1], sb + bs[i + 1]));
                } else {
                    max = Math.min(max, Math.min(sa + bs[i + 1], sb + as[i + 1]));
                }
            }
            a = (char) (97 - a);
            b = (char) (97 - b);
        }
        if (chars[length - 1] != '0') {
            sa++;
        } else {
            sb++;
        }
        return Math.min(max, Math.min(sa, sb));
    }

}
